package com.fr.lintcode;

import org.junit.Test;

/**
*作者：furong
*日期：2017年2月16日
*时间：下午5:56:58
*/
public class Q154 {
    /**
     * @param s: A string 
     * @param p: A string includes "." and "*"
     * @return: A boolean
     */
    public boolean isMatch(String s, String p) {
        int n = p.length() - count(p);
        Seg[] seg = new Seg[n];
        int point = 0;
        for (int i = 0; i < p.length(); i++) {
            char c = p.charAt(i);
            if (c == '*') {
                continue;
            } else {
                seg[point] = new Seg();
                seg[point].c = c;
                if (i + 1 < p.length()) {
                    seg[point].star = ('*' == p.charAt(i + 1));
                }
                point++;
            }
        }
        return check(s, seg, 0, 0);
    }

    private boolean check(String s, Seg[] seg, int i, int j) {
        if (i >= s.length() && j >= seg.length) {
            return true;
        }
        if (i >= s.length() || j >= seg.length) {
            return false;
        }
        char c = s.charAt(i);
        if (seg[j].star) {
            // * 可以重复使用check(s, seg, i + 1, j)，用一次check(s, seg, i + 1, j + 1)，一次也不用check(s, seg, i, j + 1)
            if (seg[j].c == '.') {
                return check(s, seg, i + 1, j + 1) || check(s, seg, i + 1, j) || check(s, seg, i, j + 1);
            } else if (seg[j].c == c) {
                return check(s, seg, i + 1, j + 1) || check(s, seg, i + 1, j) || check(s, seg, i, j + 1);
            } else {
                return check(s, seg, i, j + 1);
            }
        } else {
            if (seg[j].c == '.' || seg[j].c == c) {
                return check(s, seg, i + 1, j + 1);
            } else {
                return false;
            }
        }
    }

    private int count(String p) {
        int count = 0;
        for (char c : p.toCharArray()) {
            if (c == '*') {
                count++;
            }
        }
        return count;
    }

    class Seg {
        char c;
        boolean star;
    }

    @Test
    public void testA() {
        String s = "bbbba";
        String p = ".*a*a";
        System.out.println(isMatch(s, p));
    }
}
